import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Offer34 {
    List<List<Integer>> reslult = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return new ArrayList<>();
        }
        int currentNum = 0;
        Stack<Integer> stackPath = new Stack<>();
        findPath(root, target, currentNum, stackPath);
        return reslult;
    }

    public void findPath(TreeNode root, int target, int currentNum, Stack<Integer> stackPath) {
        if (root==null) return;
        currentNum += root.val;
        stackPath.push(root.val);
        boolean isLeaf = root.left == null && root.right == null;
        if (currentNum == target && isLeaf) {
            reslult.add(new ArrayList<>(stackPath));
        }
        if (root.left != null) findPath(root.left, target, currentNum, stackPath);
        if (root.right != null) findPath(root.right, target, currentNum, stackPath);
        stackPath.pop();
    }
}
